package LeetCode.month02.day53;

import java.util.ArrayDeque;
import java.util.Deque;

public class No117 {
    public Node connect(Node root) {
        if(root==null) return null;
        Deque<Node> queue = new ArrayDeque<>();
        queue.offer(root);
        int n = 1;
        while(!queue.isEmpty()){
            Node pre = queue.poll();
            if(pre.left!=null)
                queue.offer(pre.left);
            if(pre.right!=null)
                queue.offer(pre.right);
            while(n>1){
                Node curr = queue.poll();
                if(curr.left!=null)
                    queue.offer(curr.left);
                if(curr.right!=null)
                    queue.offer(curr.right);
                pre.next = curr;
                pre = curr;
                n--;
            }
            n = queue.size();
        }
        return root;
    }
}
